package tree;

/**
 * @description: 顺序存储二叉树(只考虑完全二叉树)：左节点 n*2+1 右节点 n*2+2 父节点：(n-1)/2
 * @title: BST
 * @author: zp
 * @date: 2021/12/4 17:43
 */
public class BST<Key extends Comparable<Key>, Value> {
    public Node root;//二叉查找树的根节点

    private class Node {
        private Key key;//键
        private Value val;//值
        private Node left, right;//指向子树的链接
        private int N;//以该节点为根的子树中的节点总数

        public Node(Key key, Value val, int N) {
            this.key = key;
            this.val = val;
            this.N = N;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    '}';
        }
    }

    /**
     * @description: 前序遍历
     * @author: zp
     * @date: 2021/12/4 17:55
     * @param: node
     * @return: void
     */
    public void preOrder(Node node) {

        if (node == null) {
            return;
        }
        System.out.println(node);
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }

    /**
     * @description: 前序遍历
     * @author: zp
     * @date: 2021/12/4 17:55
     * @param: node
     * @return: void
     */
    public void infixOrder(Node node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            infixOrder(node.left);
        }
        System.out.println(node);
        if (node.right != null) {
            infixOrder(node.right);
        }
    }

    /**
     * @description: 前序遍历
     * @author: zp
     * @date: 2021/12/4 17:55
     * @param: node
     * @return: void
     */
    public void epilogueOrder(Node node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            epilogueOrder(node.left);
        }
        if (node.right != null) {
            epilogueOrder(node.right);
        }
        System.out.println(node);
    }

    public int size() {
        return size(root);
    }

    public int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }

    public Value get(Key key) {
        return get(root, key);
    }

    //在以x为根节点的子树中查找并返回Key对应的值
    //找不到则返回Null
    private Value get(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return x.val;
        }
    }

    public void put(Key key, Value val) {
        root = put(root, key, val);
        //查找Key，找到则更新它的值，否则为他创建一个新的节点
    }

    private Node put(Node x, Key key, Value val) {
        //如果key存在于以x为根节点的子树中则更新它的值
        //否则将以Key和val为键值对的新结点插入到该子树中
        if (x == null) {
            return new Node(key, val, 1);//设为根节点，节点总数为1
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    //最小键
    public Key min() {
        return min(root).key;
    }

    public Node min(Node x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }

    //删除最小键
    //要不断深入根节点左子树中直至遇见一个空链接
    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null) {
            return x.right;
        }
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = delete(x.left, key);
        } else if (cmp > 0) {
            x.right = delete(x.right, key);
        } else {//这个节点就是要删除的节点
            if (x.right == null) {
                return x.left;//右子树为空，删除了x就只剩左子树，直接返回左子树
            }
            if (x.left == null) {
                return x.right;//左子树为空。。
            }
            Node t = x;//要删除的原节点
            x = min(t.right);//后继节点
            x.right = deleteMin(t.right);//后继节点的右子树=删除了它的 原节点右子树
            x.left = t.left;//后继节点的左子树=原节点的左子树
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
}
